<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      //这是排列问题，且每个数字可以用n次，因此不能用use，也不能用回溯。只能完全背包。如果每个数字只能用一次，那么
      //就用use，如果不是排列是组合，那么可以用回溯
      var combinationSum4 = function (nums, target) {
        let bagSize = target
        let dp = new Array(bagSize + 1).fill(0)
        dp[0] = 1
        for (let j = 0; j <= bagSize; j++) {
          for (let i = 0; i < nums.length; i++) {
            if (j >= nums[i]) {
              dp[j] += dp[j - nums[i]]
            }
          }
        }
        return dp[bagSize]
      }
      combinationSum4([1, 2, 3], 4)
    </script>
  </body>
</html>
